package code1_100.code21_30;

/**
 * @author 韩迪
 * @date 2022/03/21 22:54
 **/
public class Code24 {

     class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     }

    public ListNode swapPairs(ListNode head) {
         if (head==null)
             return null;
        //用双链表解（归并法）
        ListNode pre = head;
        ListNode tail = head.next;
        if (tail == null)
            return head;
        ListNode h = head.next.next;
        ListNode p = pre;
        ListNode t = tail;
        //拆分为两个链表
        for (int i=0;h!=null;i++){
            if(i%2==0){
                pre.next = h;
                pre=pre.next;
            }else {
                tail.next=h;
                tail=tail.next;
            }
            h = h.next;
        }
        pre.next = null;
        tail.next = null;

        //重新合并
        pre = p;
        tail = t;
        h = new ListNode();
        head = h;
        for (int i=1;tail!=null;i++){
            if(i%2==0){
                h.next = pre;
                pre = pre.next;
            }else{
                h.next = tail;
                tail=tail.next;
            }
            h = h.next;
        }
        if (pre!=null){
            h.next=pre;
        }
        return head.next;

    }

    public static void main(String[] args) {
        ListNode list1 = new Code24().new ListNode(1);
        ListNode list2 = new Code24().new ListNode(2);
        ListNode list3 = new Code24().new ListNode(3);
        ListNode list4= new Code24().new ListNode(4);
        list1.next=list2;
        list2.next=list3;
        list3.next=list4;
        list4.next=null;
        ListNode l = new Code24().swapPairs(list1);
        while (l!=null){
            System.out.println(l.val);
            l=l.next;
        }
    }
}
